A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles

首先，這篇論文要解決的就是拼圖問題，拼圖大家小時候應該都玩過。
就是給定n塊不重複的拼圖，然後重建出原圖。
他們還遇到一個困難，就是沒有一個足夠大的公開圖片集，來測試各種演算法的效能。
那這項問題也能應用在許多地方，像是生物學、考古學，
或是重建破碎的文件或照片之類的，用途十分廣泛。

這篇論文提出了第一個自動化並且有效的GA 拼圖解算器，
GA就是基因演算法(Genetic Algorithm)，
在深度學習出現以前，被廣泛應用在人工智慧領域。

主要的貢獻有三個：
他們成功在有限時間內解出了大約22000片的拼圖
還有就是對GA演算法進行了優化，讓他更適用在這個問題上面
建立了一個新的benchmark，公開給大家測試使用。

GA演算法流程：

1. 先隨機產生1000組染色體
2. 每個世代固定有1000組染色體，其餘的染色體用交配的方式產生。
   父母染色體由輪盤法挑選，每次交配產生一個後代
3. 整個GA會運行100代。

接著詳細介紹每個步驟，
他們是使用實數型GA表示染色體，
每塊拼圖在隨機初始化的時候會被編號，
每個染色體用NxM大小的矩陣表示，代表組成一張拼圖的放置順序。

這是用來計算兩張拼圖的不相似度，有點像是距離公式。
就是用Xi最後一欄的值 - Xj 第一欄的值
然後是在Lab*色彩空間計算，所以有3層。K是高度
這樣就可以求出兩片拼圖的不相似度。

這是適應函數，
就是把所有拼圖的不相似度加起來，他只有加兩個方向才不會重複計算。
他們還有建立一個表，來加快計算速度。

Crossover

我們都知道一個好的交配方法，要能夠把父母“好的特徵”傳遞給孩子。
原本GA交配方法，只是去交換染色體，可能會產生具重複和或有缺少的拼圖的染色體，所以沒辦法直接用在這裡。

前面提過，適應值是根據相鄰拼圖相似度的來計算的，
雖然一開始染色體是隨機產生的，但是我們可以合理的假設：
在幾個世代以後，將會出現一些正確組合的拼圖片段。
例如這三塊：

而這些片段是很好的特徵，應該要能傳遞給孩子。
這就是 Position independence，交配方法必須具有傳遞正確片段的能力。

這是他們提出的交配方法：

1. 選定兩個父染色體作為“顧問”，然後以kernel逐漸增長，建構出後代染色體。

2. 接著隨機選一片當作kernel起始點，放在拼圖中心點，他會從kernel周圍開始填。

3. 將拼圖一片一片的填進去，就像下面的圖越長越大塊。

4. 由於會預先知道拼圖尺寸，所以會知道有沒有填超過範圍。當他填超過範圍的時候，他會把整個kernel位移，

例如看(f) 到 (g)，因為他要填左邊的部分，所以把整個kernel往右移動，讓他可以填進去。

那要如何挑選要填入的拼圖呢？

他們分成三個階段來挑選。

首先第一階段，他會把kernel的每塊邊界用（xi，R）表示。
他們會檢查每個邊界，看是不是兩個parent 都同意某一塊拼圖要接在這個邊界上，
如果全部檢查完，只有一個邊界兩個parent都同意放某一塊拼圖，那就會填上去。
如果發現有很多邊界都可以放，他就會隨機選一個放上去，其他的忽略掉。
那如果都沒有找到可以放的邊界，就會進到下一個階段

接著，就是來找這個邊界的快樂夥伴，
簡單來說，對於這個邊界，在某一個parent裡面找不到比這一塊更適合放在他旁邊的拼圖。
例如這個公式，R1 跟 R2是互補的方向，例如上跟下，左跟右
Xi 除了 Xj 以外，找不到更適合放在他右邊的那一塊
Xj 除了 Xi 以外，找不到更適合放在他左邊的那一塊
那Xi, Xj 就可以視為快樂夥伴，那我們就會填進去。

如果都找不到快樂夥伴的話，就是第三階段，
隨機挑選一個邊界，找跟他最相似的拼圖填進去。
他這邊有提到可以加入突變，就變成隨機挑一塊拼圖填進去。

這就是整個挑選的過程，
他會依序從第一個階段到第三個階段去挑，
所以每填完一片，所以他會回到第一階段開始下一片的篩選。

評估結果的方法：

1. Direct Comparison
   直接比較有多少拼圖放到正確的原圖位置，算出正確率

2. Neighbor Comparison
   計算正確鄰居數量的比率
   直接比較的缺點是不能容忍放在不正確的位置，即使他們組合是正確的，有點偏差就會算錯。
   例如下面四張結果與原圖只有位移的差別，若用直接比較的話會得到0%，
   但是用相鄰比較會有95%以上的相似度，所以用相鄰比較評估結果比較合理。

Experimental Results

表1列出了我們的GA在不同大小拼圖的正確率。
實驗的圖像數據包含了320張，504張和805張拼圖的20張圖像組和2,360張和3,360張拼圖的3張圖像。
每張圖測試跑10次，分別列出平均最好，最差，平均，還有標準差。
可以看出儘管GA具有隨機性，每次運行的結果幾乎相同，證明了他們方法的魯棒性。

這是一些結果展示，Final的正確率是100%

表3 平均運行時間，可以看到GA的性能超越了之前的其他方法
拼圖尺寸越大，差距越大。

Future Work

他們認為他們提的方法，未來可以解決更多困難的問題，
包括未知的拼圖方向，遺漏和過多的拼圖，未知的尺寸和三維拼圖等等